Graph Traversal Techniques (DFS, BFS)

Graph Traversal হল একটি গ্রাফের প্রতিটি নোড বা শীর্ষ (vertex) এবং এর সাথে সংযুক্ত সীমান্ত (edges) পরিদর্শন করার প্রক্রিয়া। দুটি প্রধান গ্রাফ ট্রাভার্সাল কৌশল হল Depth-First Search (DFS) এবং Breadth-First Search (BFS)। এই দুটি কৌশল গ্রাফের শীর্ষগুলিকে একটি নির্দিষ্ট পদ্ধতিতে পরিদর্শন করার জন্য ব্যবহৃত হয়।

১. Depth-First Search (DFS)

DFS (Depth-First Search) হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা একটি শীর্ষ থেকে শুরু করে যতদূর সম্ভব গভীরতায় যায়, অর্থাৎ একটি শাখার শেষে পৌঁছানো না পর্যন্ত ঐ শাখার সমস্ত শীর্ষ পরিদর্শন করে এবং তারপর অন্য শাখায় চলে যায়।

DFS এর বৈশিষ্ট্য:

• Stack-based: DFS সাধারণত Stack ব্যবহার করে বাস্তবায়িত হয় (যেমন, রিকার্সন ব্যবহার করে)।
• Time Complexity: O(V + E), যেখানে V হল গ্রাফের শীর্ষের সংখ্যা এবং E হল সীমান্তের সংখ্যা।
• Space Complexity: O(V) (স্ট্যাকের কারণে)।

উদাহরণ: DFS Traversal using Recursion

import java.util.*;

public class GraphDFS {
    private Map<Integer, List<Integer>> adjList;

    public GraphDFS() {
        adjList = new HashMap<>();
    }

    // গ্রাফে একটি সীমান্ত যোগ করা
    public void addEdge(int v, int w) {
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
    }

    // DFS Traversal
    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsUtil(start, visited);
    }

    // DFS Utility Method
    private void dfsUtil(int v, Set<Integer> visited) {
        visited.add(v); // বর্তমান নোড ভিজিট করা
        System.out.print(v + " ");

        // সংশ্লিষ্ট সমস্ত শীর্ষ পরিদর্শন করা
        for (int neighbor : adjList.getOrDefault(v, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsUtil(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        GraphDFS graph = new GraphDFS();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 6);

        System.out.println("DFS Traversal starting from vertex 1:");
        graph.dfs(1);
    }
}

ব্যাখ্যা:

• addEdge(v, w): একটি সীমান্ত যোগ করা হয় যা গ্রাফের দুটি শীর্ষ v এবং w এর মধ্যে সংযোগ স্থাপন করে।
• dfsUtil(v, visited): এটি রিকার্সিভভাবে DFS ট্রাভার্সাল পরিচালনা করে।
• visited: এটি একটি সেট যা ইতিমধ্যে পরিদর্শিত শীর্ষগুলির ট্র্যাক রাখে।

আউটপুট:

DFS Traversal starting from vertex 1:
1 2 4 5 3 6 

২. Breadth-First Search (BFS)

BFS (Breadth-First Search) হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা একটি শীর্ষ থেকে শুরু করে তার সমস্ত সরাসরি প্রতিবেশী শীর্ষ পরিদর্শন করে, তারপর তাদের প্রতিবেশীদের পরিদর্শন করে এবং এই প্রক্রিয়াটি নোডগুলির স্তরের (level) ভিত্তিতে চলে।

BFS এর বৈশিষ্ট্য:

• Queue-based: BFS সাধারণত Queue ব্যবহার করে বাস্তবায়িত হয়।
• Time Complexity: O(V + E), যেখানে V হল গ্রাফের শীর্ষের সংখ্যা এবং E হল সীমান্তের সংখ্যা।
• Space Complexity: O(V) (Queue এর জন্য)।

উদাহরণ: BFS Traversal using Queue

import java.util.*;

public class GraphBFS {
    private Map<Integer, List<Integer>> adjList;

    public GraphBFS() {
        adjList = new HashMap<>();
    }

    // গ্রাফে একটি সীমান্ত যোগ করা
    public void addEdge(int v, int w) {
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
    }

    // BFS Traversal
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            int v = queue.poll(); // Queue থেকে শীর্ষ বের করা
            System.out.print(v + " ");

            // সমস্ত প্রতিবেশী পরিদর্শন করা
            for (int neighbor : adjList.getOrDefault(v, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        GraphBFS graph = new GraphBFS();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 6);

        System.out.println("BFS Traversal starting from vertex 1:");
        graph.bfs(1);
    }
}

ব্যাখ্যা:

• addEdge(v, w): গ্রাফের মধ্যে সীমান্ত যোগ করা হয়েছে।
• bfs(start): এটি BFS ট্রাভার্সাল পরিচালনা করে, যেখানে প্রথমে শীর্ষটি start থেকে শুরু হয় এবং পরে queue ব্যবহার করে প্রতিবেশী শীর্ষগুলো পরিদর্শন করা হয়।
• Queue: BFS ট্রাভার্সাল queue ব্যবহার করে, যাতে প্রথমে অ্যাড করা শীর্ষ প্রথমে পরিদর্শন হয়।

আউটপুট:

BFS Traversal starting from vertex 1:
1 2 3 4 5 6 

৩. DFS vs BFS

৪. কোথায় ব্যবহার করবেন?

• DFS (Depth-First Search):
  • Topological Sort: DFS টেকনিক ব্যবহার করে টপোলজিক্যাল সাজানো করতে সাহায্য করে।
  • Cycle Detection: গ্রাফে সাইকেল রয়েছে কিনা তা পরীক্ষা করতে DFS ব্যবহার করা হয়।
  • Pathfinding in Mazes: মেজে বা গ্রাফে পথ অনুসন্ধান করতে DFS ব্যবহৃত হয়।
• BFS (Breadth-First Search):
  • Shortest Path in Unweighted Graph: অযথা ভারী গ্রাফে (যেখানে সমস্ত সীমান্তের ওজন সমান) BFS ব্যবহার করা হয়।
  • Level-order Traversal: গাছের স্তরের মাধ্যমে অনুসন্ধান করতে BFS ব্যবহার হয়।
  • Connectivity Checking: গ্রাফের মধ্যে সংযোগ রয়েছে কিনা তা চেক করার জন্য BFS ব্যবহার করা হয়।

সারাংশ

DFS এবং BFS হল দুটি গুরুত্বপূর্ণ গ্রাফ ট্রাভার্সাল টেকনিক। DFS শীর্ষগুলোকে গভীরভাবে অনুসন্ধান করে, যেখানে BFS স্তরের মাধ্যমে অনুসন্ধান করে। জাভাতে এই দুটি অ্যালগরিদম কাস্টম গ্রাফ ইমপ্লিমেন্টেশন বা java.util লাইব্রেরির সাহায্যে খুব সহজে বাস্তবায়িত করা যায়। DFS এবং BFS এর সঠিক ব্যবহার সমস্যা অনুযায়ী নির্বাচন করতে হয়, এবং এগুলোর ব্যবহার গ্রাফের উপরের স্তর থেকে নিচের স্তরে বা যোগাযোগ পরিমাপ করতে কার্যকরী।